# import os
# import numpy as np
# from scipy.io import loadmat
#
# def check_graph_connectivity(graph):
#     """
#     检查图的连通性
#     :param graph: 稀疏矩阵表示的图
#     :return: 是否连通
#     """
#     n = graph.shape[0]
#     visited = np.zeros(n, dtype=bool)
#     queue = [0]
#     visited[0] = True
#
#     while queue:
#         u = queue.pop(0)
#         for v in graph[u].indices:
#             if not visited[v]:
#                 visited[v] = True
#                 queue.append(v)
#
#     return np.all(visited)
#
# def inspect_sparse_matrix(graph):
#     """
#     检查稀疏矩阵的非零元素
#     :param graph: 稀疏矩阵
#     """
#     print("Non-zero elements in the sparse matrix:")
#     print(graph.nonzero())
#
# def main():
#     # 设置数据目录
#     DATADIR = os.path.join(os.path.dirname(os.path.abspath(__file__)), "data/")
#
#     # 加载Yelp数据集的稀疏矩阵
#     yelp_file = os.path.join(DATADIR, 'YelpChi.mat')
#     mat_data = loadmat(yelp_file)
#     yelp_homo = mat_data['homo']
#
#     # 检查图的连通性
#     is_connected = check_graph_connectivity(yelp_homo)
#     print(f"Graph is connected: {is_connected}")
#     # 检查稀疏矩阵的非零元素
#     inspect_sparse_matrix(yelp_homo)
#
# if __name__ == "__main__":
#     main()


import os
import numpy as np
import pandas as pd
import scipy.sparse as sp
from scipy.io import loadmat
from scipy.sparse.csgraph import connected_components, shortest_path
from tqdm import tqdm


def validate_amazon_distribution():
    # 加载原始数据
    mat_path = os.path.join("data", "Amazon.mat")  # 修改为实际路径
    mat_data = loadmat(mat_path)
    sparse_matrix = mat_data['homo']

    # 预处理矩阵
    print("预处理矩阵...")
    sparse_matrix = sparse_matrix.maximum(sparse_matrix.T)  # 确保无向
    sparse_matrix.setdiag(0)  # 移除自环
    sparse_matrix = sparse_matrix.tocsr()

    # 验证连通性
    print("验证连通性...")
    n_components, labels = connected_components(sparse_matrix, directed=False)
    print(f"实际连通组件数量: {n_components}")

    # 验证最大距离的可靠性（抽样验证）
    def bfs_max_dist(node):
        """改进的BFS实现，准确计算最大距离"""
        visited = {node: 0}
        queue = [node]
        max_dist = 0

        while queue:
            current = queue.pop(0)
            current_dist = visited[current]

            # 遍历所有邻居
            neighbors = sparse_matrix[current].indices
            for neighbor in neighbors:
                if neighbor not in visited:
                    visited[neighbor] = current_dist + 1
                    max_dist = max(max_dist, current_dist + 1)
                    queue.append(neighbor)

        return max_dist

    # 随机采样100个节点进行BFS验证
    print("\nBFS抽样验证最大距离...")
    max_dists = []
    for _ in tqdm(range(100), desc="进度"):
        node = np.random.randint(0, sparse_matrix.shape[0])
        max_dists.append(bfs_max_dist(node))

    # 分析结果
    dist_counts = pd.Series(max_dists).value_counts().sort_index()
    print("\n抽样节点最大距离分布:")
    print(dist_counts)

    # 精确验证（可选）
    if input("\n是否需要精确计算直径？(y/n)").lower() == 'y':
        try:
            print("开始精确计算（可能需要较长时间）...")
            dist_matrix = shortest_path(sparse_matrix,
                                        directed=False,
                                        method='D',
                                        unweighted=True)
            max_dist = np.nanmax(dist_matrix[dist_matrix != np.inf])
            print(f"实际最大距离: {int(max_dist)}")
        except MemoryError:
            print("内存不足，无法计算全矩阵！")


if __name__ == "__main__":
    validate_amazon_distribution()